package bite;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Creared with IntelliJ IDEA.
 * Description:【求正数数组的最小不可组成和】给定一个全是正数的数组arr，定义一下arr的最小不可组成和的概念： 1，arr的所有非空子集中，把每个子集内的所有元素加起来
 * 会出现很多的值，其中最小的记为min，最大的记为max； 2，在区间[min,max]上，如果有一些正数不可以被arr某一个子集相加得到，那么这些正数中最小的那
 * 个，就是arr的最小不可组成和； 3，在区间[min,max]上，如果所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和； 举例： arr =
 * {3,2,5} arr的min为2，max为10，在区间[2,10]上，4是不能被任何一个子集相加得到的值中最小的，所以4是arr的最小不可组成和； arr = {3,2,4} arr的min为
 * 2，max为9，在区间[2,9]上，8是不能被任何一个子集相加得到的值中最小的，所以8是arr的最小不可组成和； arr = {3,1,2} arr的min为1，max为6，在区间[2,6]
 * 上，任何数都可以被某一个子集相加得到，所以7是arr的最小不可组成和； 请写函数返回arr的最小不可组成和。
 * User:yxd
 * Date:2022-05-24
 * Time:17:29
 */
public class Day29_1 {
    /**
     * 正数数组中的最小不可组成和
     * 输入：正数数组arr
     * 返回：正数数组中的最小不可组成和
     */
    public int getFirstUnFormedNum(int[] arr) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        boolean[] bool = new boolean[arr.length];
        DFS(ret,list,bool,0,arr);
        //此时ret里面存放的就是这个数组的所有子集
        int minval = Integer.MAX_VALUE;
        int maxval = Integer.MIN_VALUE;
        //存放子集的和
        Set<Integer> set = new HashSet<>();
        for (List<Integer> a:ret) {
            int sum = 0;
            for(int x : a){
                sum += x;
            }
            set.add(sum);
            //取得最大值和最小值
            maxval = Math.max(sum,maxval);
            minval = Math.min(sum,minval);
        }
        //此时在看这个区间内的所有数是不是能在set里面,如果没有就放在一个list里面,然后再从这个list里面找最小的然后输出,如果全部都在set里面那就maxval+1就是结果
        int count = Integer.MAX_VALUE;
        boolean flg = true;
        for (int i = minval; i <= maxval; i++) {
            if(!set.contains(i)){
                flg = false;
                count = Math.min(count,i);
            }
        }
        if(flg){
            return maxval + 1;
        }else{
            return count;
        }
    }
    public void DFS(List<List<Integer>> ret, List<Integer> list, boolean[] bool, int index,int[] arr) {
        if(!list.isEmpty()){
            if(list.size() <= arr.length){
                ret.add(new ArrayList<>(list));
            }else{
                return;
            }
        }
        for(int i = index;i < arr.length;i ++){
            if(!bool[i]){
                bool[i] = true;
                list.add(arr[i]);
                DFS(ret,list,bool,i + 1,arr);
                bool[i] = false;
                list.remove(list.size() - 1);
            }

        }
    }



    /**
     * 正数数组中的最小不可组成和
     * 输入：正数数组arr
     * 返回：正数数组中的最小不可组成和
     */
    public int getFirstUnFormedNum1(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = 0;
        for(int i : arr){
            //最小值
            min = Math.min(min,i);
            //最大值
            max += i;
        }
        //整个区间
        boolean[] booleans =  new boolean[max + 1];
        //初始值为0
        booleans[0] = true;
        //遍历整个数组
        for(int o : arr){
            //从最大值看起,将每一个减去o所获得的的值都设为true,就表示能由子集相加得到
            for(int j = max; j >= o;j --){
                //取其本身的ture或者减去的true
                booleans[j] = booleans[j - o] || booleans[j];
            }
        }
        for (int i = min; i < booleans.length ; i++) {
            if(!booleans[i]){
                return i;
            }
        }
        return max + 1;
    }
}
